package graph.base.mingeneratetree;

import graph.graphtype.NoDirectWeightGraph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: 26233
 * @create: 2021-11-13 21:23:41
 * @Description
 *
 * graph最小生成树算法Prim (加点法)
 * 原理:
 *  1、将节点分为两个集合u,v.开始时，u为空，v中是所有的节点
 *  2、在v中随机选取一个节点到u中，作为起始节点
 *  3、选取距离u中节点最小weight的节点(比较时，已添加的节点除开)，该节点不在u中，然后把该节点加入到u中
 *  4、重复操作3，直到v中的节点都被加到了u中
 *
 *  对于有向图，比较可行的边即可吧
 *
 **/

public class Prim {

    private NoDirectWeightGraph g;
    private Map<Integer, Integer> visited;
    private List<Integer> u;

    public Prim(NoDirectWeightGraph g) {
        this.g = g;
        visited = new HashMap<>();

        for (int i = 0; i < g.table.length; i++){
            visited.put(i, 0);
        }
        u = new ArrayList<>();
    }

    public void prime(){
        boolean first = true;
        while (u.size() != g.table.length){
            int[] minEdge = selectMin(first);
            visited.put(minEdge[1], 1);
            u.add(minEdge[1]);

            if (first){
                System.out.println("select: " + minEdge[0]);
            }else {
                System.out.println("select: " + minEdge[0] + " -> " + minEdge[1] + " ,w = " + minEdge[2]);
            }
            first = false;
        }
    }

    public int[] selectMin(boolean first){
        if (first){
            return new int[]{0, 0, 0};
        }else {

            int minIndex = 0;
            int min = Integer.MAX_VALUE;
            int src = 0;

            for (int i = 0; i < u.size(); i++){
                int[] minEdge = g.table[u.get(i)].getMinEdge(visited);
                if(visited.get(minEdge[1]) != 1 && minEdge[2] < min){
                    min = minEdge[2];
                    minIndex = minEdge[1];
                    src = minEdge[0];
                }
            }
            return new int[]{src, minIndex, min};
        }
    }

    public static void main(String[] args) {

        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
                {1, 3, 1}, {2, 3, 2}, {2, 4, 4},
                {3, 4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};
        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
        g.generateGraphBySingle(edges);
        Prim prim = new Prim(g);
        prim.prime();

    }
}
